package com.study.algorithm.strs;

import java.util.HashSet;
import java.util.Set;

/**
 * 串
 * @author jeffSheng
 *
 */
public class Strs {

	public static void main(String[] args) {
		String a="happy";
//		System.out.println(a.substring(3, 5));//py
		String b="y";
		int pos=1;
		System.out.println(findIndex(a,b,pos));
	}

	
	
	/*
	 * @date 20190615
	 * 串的模式匹配算法
	 * 
	 * child为非空串 。 若主串 parent中第 pos个字符之后将在与 child相等的子串.
	 *    则返回第一个这样的子串在parent中的位置，否则返回0 。
	 * 
	 * @param parent 主串
	 * @param child 子串
	 * @param pos 子串在主串的什么第几个位置后出现
	 * @return
	 */
	public static int findIndex(String parent,String child,int pos){
		int n,m,i;
		String sub="";
		if(pos>0) {
			n=parent.length();
			m=child.length();
			i=pos;
			while(i<=(n-m)) {
				sub=parent.substring(i, i+m);
				if(!sub.equals(child)) {
					++i;
				}else {
					return i;
				}
			}
		}
		return 0;
	}
	
	
	
	/**
	 * @date 20190615
	 * 朴素的模式匹配算法---待画图验证
	 * @param parent
	 * @param child
	 * @param pos
	 * @return
	 */
	public static int findSimpleIndex(String parent,String child,int pos){
		int i=pos;//i是主串中当前位置下标
		int j=0;
		//只要主串和子串都没有超过自己的长度，则迭代继续
		while (i<parent.length() && j<child.length()) {
			if(parent.charAt(i)==child.charAt(j)) {
				++i;
				++j;
			}else {
				i=i-j+2;//i退回到上次匹配首位的下一位
				j=0;//j退回到首位
			}
		}
		if(j>child.length()) {
			return i-child.length();
		}else {
			return 0;
		}
	}
	
	 /**
	  * 找出字符串中最大长度的字符不重复的子串长度
	  * @param s
	  * @return
	  */
	 public int lengthOfLongestSubstring(String s) {
	        int n = s.length();
	        int ans = 0;
	        for (int i = 0; i < n; i++)
	            for (int j = i + 1; j <= n; j++)
	                if (allUnique(s, i, j)) ans = java.lang.Math.max(ans, j - i);
	        return ans;
	    }
	 	/**
	 	 * 判断子字符串的字符是否都不重复
	 	 * @param s
	 	 * @param start
	 	 * @param end
	 	 * @return
	 	 */
	    public boolean allUnique(String s, int start, int end) {
	        Set<Character> set = new HashSet<>();
	        for (int i = start; i < end; i++) {
	            Character ch = s.charAt(i);
	            if (set.contains(ch)) return false;
	            set.add(ch);
	        }
	        return true;
	    }
	    
	    /**
	     * 子字符串的最大长度的第二种解法：时间复杂度是O(n)
	     * @param s
	     * @return
	     */
       public int lengthOfLongestSubstring2(String s) {
           int n = s.length();
           Set<Character> set = new HashSet<>();
           int ans = 0, i = 0, j = 0;
           while (i < n && j < n) {
               // try to extend the range [i, j]
               if (!set.contains(s.charAt(j))){
                   set.add(s.charAt(j++));
                   ans = java.lang.Math.max(ans, j - i);
               }
               else {
                   set.remove(s.charAt(i++));
               }
           }
           return ans;
       }
       
       
       /**
        * 根据字符串s对字符串t进行排序，s中没有出现的字符顺序任意
        * @param s
        * @param t
        * @return
        */
       public static String[] sortStrByOtherStr(String s,String t){
       	String[] sArr = new String[s.length()];
       	String[] tArr = new String[t.length()];
       	for (int i = 0; i < t.length(); i++) {
       		tArr[i]= String.valueOf(t.charAt(i));
			}
       	for (int i = 0; i < s.length(); i++) {
       		String x = String.valueOf(s.charAt(i));
       		sArr[i]= x;
			}
       	int j=0;
       	for (int i = 0; i < sArr.length; i++) {
       		int index =getIndexInArray(tArr,sArr[i]);
				 if(index > 0){
				     //将字符与数组第一个字符位置进行替换
					 String temp = tArr[j];
					 tArr[j] = tArr[index];
					 tArr[index] = temp;
					 j++;
				 }
			}
       	return tArr;
       }
       
       public static int getIndexInArray(String[] arr,String str){
       	for (int i = 0; i < arr.length; i++) {
				if(arr[i].equals(str)){
					return i;
				}
			}
       	return -1;
       }
}
